In many conventional printers, a "page" of print data is typically divided up into multiple "blocks" which, in turn, each contain many rows and columns of print data in the form of dots or print elements (i.e., "pels"). Such print data is typically received by a printer from a host computer in the form of a high-level page description language, which must be processed or "rasterized" to convert the page description language commands into the multitude of dots that make up the final print image. Many printers perform an intermediate conversion step in which the high-level page description language commands are partially converted into a series of commands and data that can be quickly rasterized into a final bitmap image that can be sent directly to the print engine.
In most modern conventional printers, each of the blocks for a page are treated on an individual basis, so that the bitmap image data that represents one of these blocks can be stored in the printer's memory at a separate set of memory locations quite apart from similar image data representing another one of the individual blocks. This separate storing of data is typically necessary so that the printer's microprocessor can attempt to perform multiple relatively short tasks virtually simultaneously while also handling the incoming print data being received from a host computer, recognizing the fact that the microprocessor is still a sequential operating device and must handle the rasterizing and storing of bitmap image data one data word at a time, which makes is necessary to divide a page of print image data into smaller sections (i.e., the blocks) to make it more possible to divide the microprocessor's processing time into individual discrete tasks, while also utilizing only a portion of the printer's random access memory (RAM) at one time to store some of this image data.
When a block of image data is stored in RAM, it will require as many RAM bits as there are potential dot locations in the matrix of rows and columns of that block. If the printer is a color printer, then each block will typically have four (4) planes of data to handle the four (4) different colors that will ultimately be printed for that block. If, for example, each block is 128 lines.times.512 columns in size, then its bitmap will require 65,536 bits of RAM for storage, which translates into 8 Kbytes of memory space. If the printer handles color data, then the memory requirements for that block of data will be four (4) times that memory size, or 32K. At a print resolution of 600 dots per inch (dpi), a single page of 81/2.times.11 inches would require about 500 blocks having the dimensions 128.times.512, which represents a total memory size of over 4.2 Mbytes of RAM to store this single page of data, assuming black and white dots for a monochrome printer. For a color page, this print resolution would require over 16 Mbytes of RAM.
Since typical laser printers come with a standard memory in the range of one to two (1-2) Mbytes of RAM, it is easy to see that it is impossible to store even a single complete page of bitmap image data (at any time) within the memory system of the printer. Therefore, the blocks of the page that make up each of the horizontal strips across the page are typically processed and printed as an individual set of data. In many conventional printers, there are specific places reserved in the printer's memory system to hold a complete strip (or "swath") of bitmap image data (sometimes referred to as a "band buffer"), so that this data can be processed and then printed, while another like strip or swath of bitmap image data is being processed while also being stored in memory. This second strip or swath of bitmap image data will typically also have a specific place reserved in the printer's memory system, and these especially reserved places in the printer's RAM are typically made up of contiguous memory locations that can have their data easily passed to the print engine when needed.
In conventional laser printers, blocks of image data are rasterized and stored in the printer's memory system without any compression of the data taking place until the printer realizes that it now has insufficient remaining free memory to store any further blocks of bitmap image data. If the printer can physically print the data quickly enough, then it is possible for an entire page of data to be rasterized and printed without running out of free memory, however, this will typically occur only in the most simple of documents having very few dots to be placed on the print media. The more general case is where the printer has rasterized a few blocks of image data and has stored it in the printer's RAM, and then realizes that no further blocks can be stored in the printer's RAM until either (1) some of the existing blocks have been printed, thereby freeing up that portion of the RAM, or (2) by compressing the data representing blocks that have already been stored in RAM, thereby also freeing up a portion of the memory space that previously was "busy."
When a conventional printer compresses data, it uses either software or hardware techniques. In the case where the compression is performed by a software routine, the printer's microprocessor retrieves one of the blocks of data already stored in RAM, in which this block of data presently exists as a full bitmap image in an uncompressed state, and the microprocessor will compress that data using a data compression technique (of which there can be more than one), and then stores the compressed result into another portion of RAM which should be much smaller in size than the portion of RAM from which the uncompressed block was retrieved.
If the data compression is performed by hardware, the printer's microprocessor chooses which block of data already stored in RAM will be the next block to be compressed, and will either retrieve that bitmap image block from RAM and transmit it to a hardware compression module using the processor's data and address busses (and thereby take up some memory bandwidth in doing so), or will command a Direct Memory Access (DMA) controller to retrieve the data from RAM and send it to the hardware compression module. Once that occurs, in conventional printers the microprocessor becomes idle, waiting for the compression cycle to become complete so it can store the compressed block of data before processing or rasterizing any further data. This is an inefficient utilization of the processing power of the printer's microprocessor.
An example of a printer that uses a hardware compression and decompression technique is disclosed in U.S. Pat. No. 5,483,354 (by Kessels) which discloses an image forming device that can create two-sided copies by rotating the second image through 180 degrees. This invention efficiently utilizes memory space by storing image data that does not need to be rotated in the first free memory address from front to back, and image data that must be rotated is stored in the last free memory address from back to front. A microprocessor or other computerized unit controls the operations of the buffers and memory storage devices, and there is a separate "compression device" and "decompression device." The incoming image data is first compressed before being either buffered or stored in memory, and after being retrieved from memory is decompressed before being printed.
Examples of printers that compress data using software techniques are disclosed in U.S. Pat. No. 5,479,587 (by Campbell) and U.S. Pat. No. 5,602,976 (by Cooper). Campbell discloses a printer that compresses data so as to use minimum RAM for holding a page of data. This printer contains a plurality of data compression procedures within its ROM. Three of the data compression techniques are "mode-m", "lzw", and a "lossy" compression procedure. The printer to attempts to allocate RAM for portions of the input data flow, and determines whether or not a sufficient amount of RAM is available for each allocation. A first data compression technique is performed, then tested to see if an appropriate level of compression has been achieved (by testing to see if it exceeds a predetermined threshold). If not, succeeding data compression procedures are employed and tested after each procedure is made, against the threshold. One of the objects of Campbell it to provide a page printer using data compression which is used when the on-board memory is in a state where printing cannot continue unless data compression occurs, and does so by software routines that control its microprocessor to carry out the actual compression and decompression techniques, using routines stored in ROM that contain the various types of available compression/decompression techniques. The disclosed data compression techniques are used in a sequence that is based upon the beneficial characteristics of each technique (i.e., the fastest technique is tried first), and also the choice of which data compression technique is to be used also depends upon the success or lack of success of a previously-tried technique. Image data is thereby compressed only when necessary, and then via the best suited technique.
U.S. Pat. No. 5,602,976 (by Cooper) discloses a page printer that converts input data in a page description language format into an intermediate display list format. The page is divided into strips that can be either entirely rasterized and compressed using a lossless or lossy compression technique, or it may be determined that the strip can be rasterized on the fly. Each strip is inspected and a time estimate is created by the processor and stored, so as to be certain that each strip will be rasterized quickly enough to keep up with the print engine. If the display list commands do not overflow memory during input, the complete strips are rasterized and compressed in the order in which they will be printed. If memory overflows at any point in the process, then the rasterizing times for the remaining strips may be determined or estimated and stored, without storing the raster output (in other words, the strips remain in their display list command format for the time being).
It would be advantageous for a printer to be able to operate more efficiently by eliminating the idle time of its microprocessor while waiting for a hardware compression module to perform a data compression cycle, and further to eliminate the need to compress print data by software techniques.